package com.zklh.leetcode.chain;

/**
 * k个一组进行翻转链表
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/4/10 17:29
 */
public class KReverseChain {


    public Node reverseKGroup(Node head, int k) {

        int groupCnt = 0;
        Node now = head;

        // 新的头结点
        Node newHead = head;
        // 上次翻转的末尾结点, 也就是
        Node preLast = new Node(-1);
        Node next = null;
        Node nextHead = head;
        while (now != null) {
            groupCnt++;
            // 要在这里获取next否则翻转后, next就被改变了
            next = now.next;
            if (groupCnt % k == 0) {
                preLast.next = reverseBetween(nextHead, 1,k);
                preLast = nextHead;
                nextHead = next;
                if (newHead == head) {
                    newHead = now;
                }
            }
            now = next;
        }
        return newHead;
    }


    /**
     * 反转 m -> n, 索引从1开始 m,n表示距离head n的位置
     * @param head
     * @param m
     * @param n
     */
    public Node reverseBetween(Node head, int m, int n) {

        if (m == 1) {
            return reverseN(head, n);
        }
        head.next = reverseBetween(head.next, m-1,n-1);
        return head;
    }

    /**
     * 反转 head 这个链条, 反转前n个元素,  返回翻转后的头结点
     * @param head
     * @param n
     * @return
     */
    public Node reverseN(Node head, int n) {

        if (n == 1) {
            return head;
        }
        Node last = reverseN(head, n-1);
        Node nowNode = head.next;
        Node tempNode = nowNode.next;
        nowNode.next = last;
        head.next = tempNode;
        return nowNode;
    }


    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Node now = this;
            while (now != null) {
                sb.append(now.val).append("->");
                now = now.next;
            }
            return sb.substring(0, sb.length()-2);
        }
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next=new Node(4);
        head.next.next.next.next=new Node(5);
        KReverseChain kReverseChain= new KReverseChain();
        Node tempHead = kReverseChain.reverseKGroup(head, 3);
        System.out.println(tempHead);
    }
}
